//被围绕的区域
//测试链接：https://leetcode.cn/problems/surrounded-regions/
public class Solve {
    int[] dx = {-1,1,0,0};
    int[] dy = {0,0,-1,1};
    int n,m;
    boolean[][] vis;
    public void solve(char[][] board) {
        n = board.length; m = board[0].length;
        vis = new boolean[n][m];
        //从四周的'O'出发,将能从边缘开始能到达的所有'O'对应的vis变成true
        for(int i = 0; i < n; i++) {
            if(board[i][0] == 'O') {
                dfs(board, i, 0);  //第一列
            }
            if(board[i][m-1] == 'O') {
                dfs(board, i, m-1); //最后一列
            }
        }
        for(int j = 1; j < m-1; j++) {
            if(board[0][j] == 'O') {
                dfs(board, 0, j);  //第一行
            }
            if(board[n-1][j] == 'O') {
                dfs(board, n-1, j); //最后一行
            }
        }
        for(int i = 1; i < n-1; i++) {
            for(int j = 1; j < m-1; j++) {
                if(!vis[i][j] && board[i][j] == 'O') {
                    board[i][j] = 'X';
                }
            }
        }
    }

    public void dfs(char[][] board, int i, int j) {
        vis[i][j] = true;
        for(int k = 0; k < 4; k++) {
            int x = dx[k] + i;
            int y = dy[k] + j;
            if(x >= 0 && x < n && y >= 0 && y < m && board[x][y] == 'O' && !vis[x][y]) {
                dfs(board, x, y);
            }
        }
    }
}
